The present invention relates to flash memory systems, and more particularly, to a system and method capable of sequentially writing data to a flash memory while having a high update efficiency and reading efficiency.
Compared with traditional magnetic storage devices, flash memory is cheaper and has less power consumption. However, in the flash memory, direct rewriting of a block having data stored therein is not permitted. In other words, to rewrite a block that has data already, the currently stored data must first be erased before the block can be rewritten by new data. Moreover, flash memory has a limitation of the number of erasing and writing operations thereon. If a particular block has been erased and written over certain number of times such as 100K times, the particular block will be damaged, and will be unable to correctly store data. Additionally, flash memory may have some bad blocks formed during the manufacturing process in the factory, or caused by excessive usage by the user. In general, flash memory's access is managed through an FFS (Flash File System, FFS). The FFS is capable of dispersing the erasing and writing operations on different blocks in order to reduce the probability of some particular blocks being overused, and to avoid using the bad blocks.
According to a Mapping Table, this flash file system (FFS) translates the logic address into the flash memory's physical address, and then writes data into the block to which the physical address points. The upper of the file system, such as FAT, access the file system randomly, not sequentially, resulting in data being randomly written into the flash memory. However, for the sake of promoting the data reliability of the flash memory, flash memory factories, such as Toshiba, have announced that the new generation of NAND flash memory only allows data to be written sequentially into physical blocks. Therefore, former flash file system (FFS) cannot satisfy this requirement.
FIG. 1 shows mapping virtual blocks 12 onto physical blocks 14 by using the Mapping Table 10. As shown in FIG. 1, a flash memory has a plurality of physical blocks 14 (block 0 to block n), and each of the physical blocks 14 contains a plurality of physical pages 16. The basic erase unit in a flash memory is one physical block. In other words, if the erasing operation is performed, all of data stored in the physical block will be erased. Additionally, the basic write unit for a flash memory is one physical page. In other words, data is written into the flash memory by writing page by page.
The related art FFS uses Block-Mapping to map the virtual blocks onto the physical blocks. In other words, the basic mapping unit is one block. As shown in FIG. 1, the number of virtual blocks 12 is equal to the number of physical blocks 14. However, it should be noted that in some embodiments, the number of virtual blocks is not equal to the number of physical blocks. Each of the virtual blocks 12 has its virtual block address, and each of the physical blocks 14 has its physical block address. FIG. 2 is a detailed diagram of the Mapping Table 10. The Mapping Table 10 has a plurality of mapping data 18. Each of the mapping data 18 stores one virtual block address and one physical block address, to establish a mapping relation between a virtual block 12 and a physical block 14. According to FIG. 2, the virtual block with the virtual block address equaling to 1 is mapped onto the physical block with the physical block address equaling to 81. Because of some bad blocks in flash memory, the number of usable physical blocks might be smaller than the number of virtual blocks. Additionally, care must be taken to avoid frequently writing and erasing one particular block, which would result in the reduced life of the particular block. So the Mapping Table 10 needs to change its stored mapping relations between virtual blocks and physical blocks according to different situations, to achieve the goal of not using the bad blocks and not overusing some particular blocks.
As shown in FIG. 1, each physical block 14 has a plurality of physical pages 16. In the same way, each virtual block 12 has a plurality of virtual pages 20. The number of physical pages 16 in one physical blocks 14 is equal to the number of virtual pages 20 in one virtual block 12. Furthermore, each physical page 16 has its physical page offset value, and each virtual page 20 has its virtual page offset value. When one of the virtual blocks 12 is mapped onto one of the physical blocks 14, each of the virtual pages 20 in the virtual blocks 12 is mapped one by one onto each of the physical pages 16 in the physical blocks 14, where one virtual page 20 having a specific virtual page offset value is mapped onto one physical page 16 whose physical page offset value is equal to the specific virtual page offset value.
FIG. 3 shows operation of the related art block mapping. For example, assume that each physical block 14 includes thirty-two physical pages 16, and each virtual block 12 includes thirty-two virtual pages 20. To find out the physical page mapped to the virtual page whose virtual page number is equaling to 161, the following steps have to be performed. First, divide the virtual page number, 161, by the number of pages per block, which is 32, to get a quotient A which is equal to five and a remainder B which is equal to one. The quotient A represents a virtual block address, and the remainder B represents a virtual page offset value. In this case, we have the equation: 161=5*32+1. So the virtual address of a virtual block containing the searched page is first determined. In this case, the virtual block address is five. The Mapping Table 10 is then used to locate a physical block whose physical block address is mapped onto the virtual block having virtual block address equaling five. Therefore, the physical block with the physical block address equaling to three is found. Then, use the virtual page offset value, which is one in this case, to search the physical block for the physical page, which has a physical page offset value equaling to one also.
Because the Mapping Table only contains the relations between the virtual blocks and the physical blocks, it doesn't need a large memory space. However, the new generation of flash memory demands for writing data sequentially, and in this situation, using the above mentioned mapping method causes a low update efficiency problem.
Writing data sequentially means that in a specific physical block, physical pages having smaller physical page offset values must be written prior to those having greater physical page offset values. In other words, before writing data into the physical page having offset value equaling to n, it must first be checked if data have been written in any of the physical pages having offset values greater than n. If there is data stored in any of the physical pages having offset values greater than n, this means that the physical block has already been written with data in the physical page(s) having offset value(s) greater than n. If data is still written into the physical page having offset value equal to n, this will violate the rule for new generation flash memories to write data sequentially. This is because writing data sequentially requires writing data into a later physical page whose physical page offset value must be greater than that of any other previously written physical page.
In this scenario, before writing data into the physical page having physical page offset value equal to n, if it is found that there is already another physical page, whose physical page offset value is greater than n, having been written with data, a new physical block has to be located. After locating the new physical block, the file system has to sequentially copy data from original physical pages with physical page offset values smaller than n in that physical block and write the data into new physical pages with physical page offset values smaller than n in the new physical block, and then write data into the new physical page having physical page offset value equal to n in the new physical block, and finally sequentially copy data from original physical pages with physical page offset values greater than n in that physical block and write the data into new physical pages with physical page offset values greater than n in the new physical block. Therefore, the requirement of writing data sequentially is met. In the mentioned scenario, in order to update one physical page's data in one physical block, the system has to move a large amount of data and perform data erasing, causing the low update efficiency problem and an increased probability of damaging blocks in the flash memory.
FIG. 4 shows how to update a physical page. Assume that the system wants to write data into the physical page of physical page offset value being 3 (page 3 or the fourth page). Even though the fourth page is empty (never been written before), writing data into the fourth page is prohibited because the physical pages having higher physical page offset values have already been written. Therefore, writing data into the fourth page will not satisfy the rule of writing data sequentially. The FFS must ask for a new physical block, and then copy all data stored in the pages before the fourth page to the new physical block (the first step), then write data into the fourth page of the new block (the second step), then copy all data stored in the pages after the fourth page (the third step), then erase all pages in the original physical block (the fourth step), and finally update the Mapping Table to map the virtual block to the new physical block (the fifth step). After finishing the above five steps, the whole update process is finished. Therefore, in order to update one physical page, all data stored in the pages of one physical block must be copied to the pages in another new physical block. In other words, every time the data update is performed, the system has to execute the action of copying and erasing, which lowers the update efficiency, and might increase the number of bad blocks in the flash memory.
In order to solve the above problems, as indicated by M-System INC., et al. in U.S. Pat. No. 6,678,785, a method of sequentially writing data into a flash memory is introduced to improve the update efficiency. FIG. 5 shows another related art method of sequentially writing data into a flash memory. When the system wants to update the physical page of physical page offset value being three (the fourth page) in one physical block, no matter the fourth page is empty or not and the physical pages after the fourth page are empty or not, the system will search from the first page to judge whether there is any empty physical page in the physical block. If there is any empty physical page in the physical block, the system writes data into the first found empty physical page. If there isn't, the FFS will ask for a new physical block and write data into the first physical page in the new physical block. In other words, unless the fourth page happens to be the first found empty physical page, no matter whether writing to the original physical block's empty page or the first page of the newly found physical block, the physical page offset value of the physical page storing the data doesn't have the same value as the virtual page offset value of the mapped virtual page. That is, the physical page and the virtual page don't have the fixed offset relation anymore. Therefore one virtual block will be mapped onto at least one physical block, resulting in a one-to-many mapping relation between physical pages and virtual pages. This mapping relation will remain until there is no empty physical block in the system, or will be compacted into one-to-one mapping relation when one virtual block is mapped to too many physical blocks.
Because the above related art method involves writing data directly into the empty physical page, it doesn't need to copy and erase data, so not only data are sequentially written, but also the update efficiency is enhanced. In addition, the times of erasing data in the blocks of the flash memory are reduced accordingly. However, when the system wants to find one physical page, it uses the Mapping Table to find out the mapped physical block, and then has to search all the physical pages in the physical block one by one until it finds the wanted physical page. This is because the virtual page and the physical page don't have the same offset value. The reading efficiency will be greatly worsened. To avoid searching one page by one page, an additional record field of the Mapping Table needs to be created. In other words, the relation between the physical page and virtual page must be built in the Mapping Table. Since the number of physical pages (or virtual pages) is much greater than the number of physical blocks (or virtual blocks), a large space is required by the Mapping Table. Additionally, the recorded mapping relationship between physical pages and virtual pages increases the complexity of searching. In other words, using the related art method disclosed by M-System INC. impairs the reading efficiency, requiring a large amount of memory space and increases the searching complexity.